﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <chrono>
#include <utility>
#include <queue>

using namespace std;

// ============================================================================
// 实验1：互斥锁（Mutex）基础 - 保护共享资源
// ============================================================================
// 【实验目的】
// 1. 理解多线程环境下的数据竞争问题
// 2. 学习使用 mutex 保护共享资源（cout 输出流）
// 3. 对比锁的粒度（循环外加锁 vs 循环内加锁）对性能和并发度的影响
//
// 【实验方法】
// 1. 创建两个线程，同时打印 0-100 的数字
// 2. 不加锁时：输出会交错混乱
// 3. 循环外加锁：一个线程完整输出后，另一个线程才开始（串行化）
// 4. 循环内加锁：每次输出都加锁，线程交替执行（细粒度锁）
// ============================================================================
/*
void func(int n, mutex& mtx) {
    mtx.lock();     // 方案A：循环外加锁 - 锁粒度大，线程串行执行
    for (int i = 0; i <= n; i++) {
        // mtx.lock();      // 方案B：循环内加锁 - 锁粒度小，线程频繁切换
        cout << this_thread::get_id() << ": " << i << endl;
        // mtx.unlock();    // 方案B：循环内解锁
    }
    mtx.unlock();   // 方案A：循环外解锁
}

int main() {
    mutex mtx;
    thread t1(func, 100, ref(mtx));  // ref() 传递引用，避免拷贝
    thread t2(func, 100, ref(mtx));

    t1.join();  // 等待线程结束
    t2.join();

    return 0;
}
*/

// ============================================================================
// 实验2：条件变量（Condition Variable）- 线程间协作（初始版本）
// ============================================================================
// 【实验目的】
// 1. 学习使用条件变量实现线程间的同步通信
// 2. 实现两个线程交替打印奇数和偶数
// 3. 理解 wait() 和 notify_one() 的基本用法
//
// 【实验方法】
// 1. 使用 bool flag 作为状态标志：true 允许打印奇数，false 允许打印偶数
// 2. t1 线程打印奇数，打印后切换 flag 并通知 t2
// 3. t2 线程打印偶数，打印后切换 flag 并通知 t1
//
// 【存在的问题】
// Lambda 捕获使用了值捕获 [flag]，导致捕获的是副本而非引用
// 这会使谓词无法正确检测 flag 的变化！（这是一个常见错误）
// ============================================================================
/*
int main() {
    mutex mtx;
    condition_variable cv;
    bool flag = true;

    thread t1([&]() {
        int i = 1;
        while (i <= 100) {
            unique_lock<mutex> ul(mtx);
            cv.wait(ul, [flag]() {return flag; });  // ❌ 错误：值捕获
            cout << this_thread::get_id() << ":" << i << endl;
            i += 2;
            flag = false;
            cv.notify_one();
        }
    });

    thread t2([&]() {
        int j = 2;
        while (j < 100) {
            unique_lock<mutex> ul(mtx);
            cv.wait(ul, [flag]() {return !flag; });  // ❌ 错误：值捕获
            cout << this_thread::get_id() << ":" << j << endl;
            j += 2;
            flag = true;
            cv.notify_one();
        }
    });

    t1.join();
    t2.join();

    return 0;
}
*/

// ============================================================================
// 实验3：条件变量（Condition Variable）- 正确的实现（修正版）
// ============================================================================
// 【实验目的】
// 1. 修正实验2中的引用捕获问题
// 2. 深入理解条件变量的工作机制（wait 的原子操作）
// 3. 掌握 RAII 和 unique_lock 的配合使用
//
// 【实验方法】
// 1. 使用引用捕获 [&flag] 确保访问的是共享变量
// 2. wait() 的工作流程：
//    - 检查谓词，如果为 false，释放锁并阻塞
//    - 被 notify 唤醒后，重新获取锁，再次检查谓词
//    - 谓词为 true 时才继续执行
// 3. unique_lock 相比 lock_guard 更灵活，支持手动解锁和与条件变量配合
//
// 【关键考点】
// - unique_lock 每次循环都重新创建，保证锁在 wait 期间能正确释放和重获
// - 必须使用引用捕获 [&flag]，否则谓词检查的是副本
// - notify_one() 只唤醒一个等待线程，notify_all() 唤醒所有等待线程
// ============================================================================
/*
int main() {
    // 共享资源 1：互斥锁，用于保护共享数据（flag）和临界区
    mutex mtx;
    // 共享资源 2：条件变量，用于线程间高效的等待和通知
    condition_variable cv;
    // 共享状态标志：控制交替执行的"红绿灯"，true 允许 t1 跑，false 允许 t2 跑
    bool flag = true;

    // 线程 t1：负责打印奇数
    thread t1([&]() {
        int i = 1;
        while (i <= 100) {
            // **RAII 考点：** 每次循环都创建 unique_lock，保证锁在 wait 期间能被释放和重获
            unique_lock<mutex> ul(mtx);

            // **核心同步机制：** wait 函数会原子性地：
            // 1. 检查谓词（Lambda）：如果返回 false，释放锁并阻塞线程。
            // 2. 被唤醒后，重新获取锁，并再次检查谓词。
            // **陷阱考点：** 必须使用引用捕获 [&flag]，确保访问的是外部的共享变量
            cv.wait(ul, [&flag]() {return flag; });

            // 临界区：打印当前奇数
            cout << this_thread::get_id() << ":" << i << endl;

            i += 2;
            // 切换状态：允许偶数线程 t2 运行
            flag = false;

            // **通知机制：** 唤醒一个正在等待 cv 的线程（即 t2）
            cv.notify_one();
        }
    });

    // 线程 t2：负责打印偶数
    thread t2([&]() {
        int j = 2;
        // 注意：t2 的循环条件 j < 100 意味着它会打印到 98
        while (j < 100) {
            unique_lock<mutex> ul(mtx);

            // 等待条件满足：只有当 flag 为 false 时才继续执行
            cv.wait(ul, [&flag]() {return !flag; });

            // 临界区：打印当前偶数
            cout << this_thread::get_id() << ":" << j << endl;

            j += 2;
            // 切换状态：允许奇数线程 t1 运行
            flag = true;

            // 唤醒等待的奇数线程 t1
            cv.notify_one();
        }
    });

    // **线程管理：** 主线程等待 t1 和 t2 线程执行完毕
    t1.join();
    t2.join();

    return 0;
}
*/

// ============================================================================
// 实验4：死锁（Deadlock）演示 - 典型的死锁场景
// ============================================================================
// 【实验目的】
// 1. 演示经典的死锁场景：两个线程以不同顺序获取同一组锁
// 2. 理解死锁的四个必要条件：互斥、占有且等待、不可抢占、循环等待
// 3. 观察死锁发生时程序的表现（阻塞，无法继续）
//
// 【实验方法】
// 1. 创建两个全局互斥锁 mtx1 和 mtx2
// 2. func1：先锁 mtx1，延时后再锁 mtx2
// 3. func2（注释版本）：先锁 mtx2，延时后再锁 mtx1 → 形成循环等待 → 死锁！
// 4. func2（运行版本）：与 func1 顺序相同，不会死锁（统一加锁顺序是避免死锁的方法之一）
//
// 【死锁发生过程】（使用注释的 func2 版本时）
// Time | Thread 1                  | Thread 2
// -----|---------------------------|---------------------------
// t0   | 获取 mtx1                 | 获取 mtx2
// t1   | sleep 100ms               | sleep 100ms
// t2   | 尝试获取 mtx2（阻塞）     | 尝试获取 mtx1（阻塞）
// t3   | 永久等待 mtx2             | 永久等待 mtx1  ← 死锁！
// ============================================================================
/*
mutex mtx1;
mutex mtx2;

void func1() {
    cout << "Thread 1 trying to lock mtx1 ...\n";
    lock_guard<mutex> lock1(mtx1);
    cout << "Thread 1 locked mtx1\n";
    this_thread::sleep_for(chrono::milliseconds(100));  // 模拟其他操作
    cout << "Thread 1 trying to lock mtx2 ...\n";
    lock_guard<mutex> lock2(mtx2);  // 在此可能阻塞
    cout << "Thread 1 acquired both locks.\n";
}

// 【版本A：会造成死锁】与 func1 加锁顺序相反
// void func2() {
//     cout << "Thread 2 trying to lock mtx2 ...\n";
//     lock_guard<mutex> lock2(mtx2);
//     cout << "Thread 2 locked mtx2\n";
//     this_thread::sleep_for(chrono::milliseconds(100));
//     cout << "Thread 2 trying to lock mtx1 ...\n";
//     lock_guard<mutex> lock1(mtx1);  // 在此阻塞，与 func1 形成循环等待
//     cout << "Thread 2 acquired both locks.\n";
// }

// 【版本B：不会死锁】与 func1 加锁顺序相同
void func2() {
    cout << "Thread 2 trying to lock mtx1 ...\n";
    lock_guard<mutex> lock1(mtx1);
    cout << "Thread 2 locked mtx1\n";
    this_thread::sleep_for(chrono::milliseconds(100));
    cout << "Thread 2 trying to lock mtx2 ...\n";
    lock_guard<mutex> lock2(mtx2);
    cout << "Thread 2 acquired both locks.\n";
}

int main() {
    thread t1(func1);
    thread t2(func2);

    t1.join();
    t2.join();
    return 0;
}
*/

// ============================================================================
// 实验5：避免死锁 - 使用 std::lock() 原子性获取多个锁
// ============================================================================
// 【实验目的】
// 1. 学习使用 std::lock() 同时获取多个锁，避免死锁
// 2. 理解 adopt_lock 参数的作用（告诉 lock_guard 锁已被获取，只需管理）
// 3. 了解 scoped_lock（C++17）的便捷用法
//
// 【实验方法】
// 1. 使用 std::lock(mtx1, mtx2) 原子性地获取两个锁（内部使用算法避免死锁）
// 2. 使用 lock_guard 配合 adopt_lock 管理已获取的锁（RAII 自动释放）
// 3. 可选：使用 scoped_lock 一步到位（自动调用 std::lock 并管理）
//
// 【关键知识点】
// - std::lock() 会使用死锁避免算法（如银行家算法）确保不会死锁
// - adopt_lock：表示锁已经被获取，lock_guard 只负责释放
// - scoped_lock<mutex1, mutex2, ...>：C++17 新特性，自动调用 std::lock
// ============================================================================
/*
mutex mtx1;
mutex mtx2;

void func1() {
    // 方法1：std::lock + lock_guard + adopt_lock
    lock(mtx1, mtx2);  // 原子性地获取两个锁（使用死锁避免算法）
    lock_guard<mutex> lock1(mtx1, adopt_lock);  // adopt_lock：锁已获取，只需管理
    lock_guard<mutex> lock2(mtx2, adopt_lock);

    cout << "Thread 1 acquired both locks.\n";
    // lock_guard 析构时自动释放锁
}

void func2() {
    // 方法2：scoped_lock（C++17 推荐）自动调用 std::lock 并管理
    // scoped_lock guard(mtx1, mtx2);  // 一行搞定，等价于上面的 lock + lock_guard

    // 方法1：与 func1 相同的实现
    lock(mtx1, mtx2);
    lock_guard<mutex> lock1(mtx1, adopt_lock);
    lock_guard<mutex> lock2(mtx2, adopt_lock);

    cout << "Thread 2 acquired both locks.\n";
}

int main() {
    thread t1(func1);
    thread t2(func2);

    t1.join();
    t2.join();
    return 0;
}
*/

// ============================================================================
// 实验6：生产者-消费者模型 - 有界阻塞队列（Bounded Blocking Queue）
// ============================================================================
// 【实验目的】
// 1. 实现经典的生产者-消费者并发模型
// 2. 综合运用互斥锁、条件变量、队列，构建线程安全的有界队列
// 3. 理解"满则阻塞"和"空则阻塞"的同步机制
// 4. 学习完美转发（perfect forwarding）在并发容器中的应用
//
// 【实验方法】
// 1. 设计 BoundedQueue 类：
//    - 队列满时，生产者调用 push() 会阻塞，直到有空间
//    - 队列空时，消费者调用 pop() 会阻塞，直到有数据
// 2. 使用两个条件变量：
//    - not_full_cv_：队列未满时唤醒生产者
//    - not_empty_cv_：队列非空时唤醒消费者
// 3. 生产者线程：每 200 微秒生产一个数据
// 4. 消费者线程：每 500 微秒消费一个数据（速度慢于生产者）
//
// 【关键技术点】
// - 完美转发 std::forward<U>(item)：支持左值和右值引用，避免不必要的拷贝
// - 移动语义 std::move：从队列取出数据时使用移动而非拷贝
// - 两个条件变量分离等待条件，避免虚假唤醒（spurious wakeup）的影响
// ============================================================================

template<typename T>
class BoundedQueue {
public:
    // 构造函数：指定队列的最大容量
    BoundedQueue(size_t size) : max_size_(size) {}

    // push：生产者接口，支持完美转发（左值/右值均可）
    template<typename U>
    void push(U&& item) {
        unique_lock<mutex> lock(mtx_);
        // 等待队列未满：lambda 返回 true 时才继续执行
        not_full_cv_.wait(lock, [this]() { return queue_.size() < max_size_; });

        // 将数据入队（完美转发，支持移动语义）
        queue_.push(forward<U>(item));

        // 通知消费者：队列非空了
        not_empty_cv_.notify_one();
    }

    // pop：消费者接口，队列为空时阻塞
    T pop() {
        unique_lock<mutex> lock(mtx_);
        // 等待队列非空：lambda 返回 true 时才继续执行
        not_empty_cv_.wait(lock, [this]() { return !queue_.empty(); });

        // 取出队首元素（使用移动语义避免拷贝）
        T item = move(queue_.front());
        queue_.pop();

        // 通知生产者：队列有空间了
        not_full_cv_.notify_one();
        return item;
    }

private:
    size_t max_size_;                    // 队列最大容量
    queue<T> queue_;                     // 底层队列容器
    mutex mtx_;                          // 保护队列的互斥锁
    condition_variable not_empty_cv_;    // 条件变量：队列非空
    condition_variable not_full_cv_;     // 条件变量：队列未满
};

int main() {
    // 创建容量为 5 的有界队列
    BoundedQueue<int> bq(5);

    // 生产者线程：生产 10 个数据
    thread producer([&]() {
        for (int i = 0; i < 10; i++) {
            bq.push(i);  // 队列满时会阻塞
            cout << "Produced " << i << endl;
            this_thread::sleep_for(chrono::microseconds(200));  // 生产速度快
        }
        });

    // 消费者线程：消费 10 个数据
    thread consumer([&]() {
        for (int i = 0; i < 10; i++) {
            int item = bq.pop();  // 队列空时会阻塞
            cout << "Consumed " << item << endl;
            this_thread::sleep_for(chrono::microseconds(500));  // 消费速度慢
        }
        });

    // 等待两个线程执行完毕
    producer.join();
    consumer.join();

    return 0;
}

// ============================================================================
// 实验总结
// ============================================================================
// 本代码集涵盖了 C++ 多线程编程的核心知识点：
// 1. 互斥锁（mutex）：保护共享资源，防止数据竞争
// 2. 条件变量（condition_variable）：线程间高效通信和同步
// 3. 死锁问题：产生原因和两种避免方法（统一顺序、std::lock）
// 4. 生产者-消费者模型：有界阻塞队列的完整实现
// 5. RAII 思想：lock_guard、unique_lock、scoped_lock
// 6. 移动语义和完美转发：提升并发容器性能
//
// 学习建议：
// - 逐个取消注释运行每个实验，观察输出结果
// - 尝试修改参数（如锁的位置、队列大小、线程速度）观察行为变化
// - 使用调试器或日志跟踪线程的执行顺序
// ============================================================================